/**
 * @file Random.hpp
 *
 *  @date 2009-03-07
 *  @author hauleth
 */

#ifndef RANDOM_HPP_
#define RANDOM_HPP_

#include <ctime>
#include <exception>

#define	BUST_RAND_MAX	9223372036854775807ull

namespace bust {
namespace {

typedef unsigned int seed_t;

class badRand: public std::exception {
	private:
		const char* err;
	public:
		badRand( const char* _err ) :
			err( _err ) {
		}
		virtual const char* what() const throw() {
			return err;
		}
};

class lcg {
	private:
		static unsigned long long int pow( int a, int b ) {
			unsigned long long int tmp = 1;
			for( int i = 0; i < b; i++ )
				tmp *= a;
			return tmp;
		}

		lcg() {
		}
		unsigned long long int seed;

		unsigned long long mult( unsigned long long a, unsigned long long x,
				unsigned long long m ) {
			unsigned long long b, n, r;

			r = 0;
			n = 1;
			b = 1;
			while( n <= 64 ) {
				if( ( a & b ) != 0 )
					r = ( r + x ) % m;
				x = ( x + x ) % m;
				b *= 2;
				n++;
			}

			return r;
		}
	public:
		static lcg& instance() {
			static lcg inst;
			return inst;
		}
		static void setSeed( seed_t _seed ) {
			instance().seed = _seed;
		}
		unsigned long int rand() {
			seed = ( mult( 1103515245, seed, pow( 2, 32 ) ) + 12345 ) % pow( 2,
					32 );
			return seed;
		}
};

/**
 * @class MT19937
 * @brief PRNG class for Merresne-Twister 19937
 * It's singleton class what random numbers using MT19937
 */
class mt19937 {
	private:
		seed_t seed;
		unsigned long long int MT[623];
		int index;
		///Hidden constructor
		mt19937() :
			index( 0 ), prepared( false ) {
		}
		void prepare() {
			unsigned long long int x = 0;

			MT[0] = seed;
			for( int i = 1; i < 623; i++ ) {
				x = MT[i - 1];
				x = ( 23023 * x ) & 0xffffffffull;
				x = ( 3 * x ) & 0xffffffffull;
				MT[i] = x;
			}
		}
		bool prepared; ///< Is already prepared?
	public:
		static mt19937& instance() {
			static mt19937 inst;
			return inst;
		}
		static void setSeed( seed_t _seed ) {
			instance().seed = _seed;
		}
		unsigned long long int rand() {
			if( !prepared ) {
				prepare();
				prepared = true;
			}
			const unsigned int MA[] = { 0, 0x9908b0df };
			long int y;
			int i1, i397;
			i1 = index + 1;
			//if( i1 > 623 )
				//i1 = 0;
			i397 = ( index + 397 ) > 623 ? index - 227 : index + 397;
			y = ( MT[index] & 0x80000000 ) | ( MT[i1] & 0x7fffffff );
			MT[index] = MT[i397] ^ ( y >> 1 ) ^ MA[y & 1];
			y = MT[index];
			y ^= y >> 11;
			y ^= ( y << 7 ) & 0x9d2c5680;
			y ^= ( y << 15 ) & 0xefc60000;
			y ^= y >> 18;
			index = i1 % 623;
			return y;
		}
};

class lfg {
	protected:
		seed_t seed;
		int pos;
		unsigned long long int x[110];
		const int J, K, A;
		const unsigned long long M;
		void prepare() {
			x[0] = seed;
			for( int i = 1; i < 110; i++ )
				x[i] = ( A * x[i - 1] ) % M;
		}
		lfg() :
			pos( 0 ), J( 24 ), K( 55 ), A( 69069 ), M( 0x100000000ull ),
					prepared( false ) {
		}
		bool prepared;
	public:
		virtual unsigned long long int rand() = 0;
};

class alfg: lfg {
	public:
		unsigned long long int rand() {
			if( !prepared ) {
				prepare();
				prepared = true;
			}
			unsigned long long result;
			x[pos] = ( x[ ( K + pos - J ) % K] + x[pos] ) % M;
			result = x[pos];
			pos = ( pos + 1 ) % K;
			return result;
		}
		static alfg& instance() {
			static alfg ret;
			return ret;
		}
		static void setSeed( seed_t _seed ) {
			instance().seed = _seed;
		}
};

class mlfg: lfg {
	public:
		unsigned long long int rand() {
			if( !prepared ) {
				prepare();
				prepared = true;
			}
			unsigned long long result;
			x[pos] = ( x[ ( K + pos - J ) % K] * x[pos] ) % M;
			result = x[pos];
			pos = ( pos + 1 ) % K;
			return result;
		}
		static mlfg& instance() {
			static mlfg ret;
			return ret;
		}
		static void setSeed( seed_t _seed ) {
			instance().seed = _seed;
		}
};

class tgfsr: lfg {
	public:
		unsigned long long int rand() {
			if( !prepared ) {
				prepare();
				prepared = true;
			}
			unsigned long long result;
			x[pos] = ( x[ ( K + pos - J ) % K] ^ x[pos] ) % M;
			result = x[pos];
			pos = ( pos + 1 ) % K;
			return result;
		}
		static tgfsr& instance() {
			static tgfsr ret;
			return ret;
		}
		static void setSeed( seed_t _seed ) {
			instance().seed = _seed;
		}
};

template < typename T >
unsigned long long int randomize( unsigned long long int from = 0,
		unsigned long long int to = BUST_RAND_MAX ) throw(badRand ) {
	if( from > to )
		throw badRand( "Bad parameters" );
	return from + T::instance().rand() % ( to - from + 1 );
}

}
}

#endif /* RANDOM_HPP_ */
